HW 03: Integer Program formulation homework 1. Implement fixed-cost/road-building in the Min Cost Network Flow little problem we've been using; adjust the $1000-to-build-a-road price until it just barely makes a difference to the optimal solution vs. having no building cost. Something unexpected might happen. Explain what it is, and why it happens. Optional: reformulate the question (not just the IP) to make the road-building decision a less obvious one. You'll need to either alter the network or the capacities or flow amounts or prices. 2. Consider just a single road rather than a whole network (ignore the little 4-town network we've been using). Suppose it costs $1000 to build the road and a further $500 per unit of flow on the road, up to 3 units of flow. Make a graph with x=flow, y=total cost. Be careful with open-circle and closed-circle points. This is meant to be a very simple problem, rather than a long and involved one. You won't be using Solver at all. It's actually somewhat hard to get a decent graph of it done in Excel or Python or most software. You could sketch it on paper, take a picture, and embed that in your homework file. Or you could sketch it using Microsoft Paint or equivalent. Or you could sketch it on paper, then describe it in a sentence or two instead of including the picture in your homework file. 3. Recall the Sailco problem; make overtime in each month cost $300/boat instead of $450/boat (that is, more like a bulk discount rather than an extra cost), with the restriction that no overtime can be used in a month unless the regular-time production is fully used in that month. 4. Like question 2 above, now consider just one month's production for Sailco (ignore the rest of the Sailco problem). Graph x=#boats produced and y=total cost using the $300/each for overtime production from problem 3, above. Again this should be a simple problem, not involving Solver. See the advice above about sketching. 5. Suppose you have cities at these locations: x y 1 10 4 14 4 6 17 10 14 14 14 6 Here is the distance matrix (the distance from each city to each other city): 0.0 5.0 5.0 16.0 13.6 13.6 5.0 0.0 8.0 13.6 10.0 12.8 5.0 8.0 0.0 13.6 12.8 10.0 16.0 13.6 13.6 0.0 5.0 5.0 13.6 10.0 12.8 5.0 0.0 8.0 13.6 12.8 10.0 5.0 8.0 0.0 Let's formulate the Travelling Salesperson Problem (TSP) this way: define x_ij = 1 if we drive from city i to city j, and 0 otherwise. We will constrain c_ii=0 for each city (that is, we can't drive from a city to itself). In Solver, implement this model to minimize the total driving distance to visit all cities. Once it's solved, you will discover a problem with this formulation. Say what the problem is. 6. Regarding "OR" instead of "AND" constraints: a) how would you implement having one constraint OR another, rather the "AND" that we're used to? For example, 3*x + 5*y <= 15 _OR_ 7*x + 2*y <= 14 ? b) Graph the feasible region for part (a), along with x>=0, y>=0. Comment on its shape. c) how would you implement: job A's length is 13 minutes; job B's length is 19 minutes. Schedule a start time for job A and a start time for job B so they don't overlap. Jobs may start at any time between 0 and 100. Imagine this is part of a bigger problem (with jobs C, D, E, ...) so we can't just decide on our own to schedule A first then B, we want the solver to figure out which to schedule when. 7. At least one of the problems above has a problem with symmetry, and would benefit from symmetry-breaking constraints to help it solve more quickly. Which one is it? Explain how you know. 8. (optional) Compressive Sensing/Compressed Sensing: this is a hot topic these days in applied math. It involves minimizing the number of nonzero coefficients used in something like linear regression or Fourier analysis. If you want me to get you started on this, let me know. Great Reading about Integer Programming: http://www.inf.ufpr.br/aurora/disciplinas/topicosia2/livros/search/integer.pdf http://www.sce.carleton.ca/faculty/chinneck/po/Chapter13.pdf Integer Programming: The Global Impact by Nemhauser https://smartech.gatech.edu/handle/1853/49829 Mike Trick's blog on sports scheduling, solvers taking over from reformulations, etc. http://mat.tepper.cmu.edu/blog/?p=1832 http://mat.gsia.cmu.edu/trick/formul04.pdf Travelling Salesperson Problem reading: http://punkrockor.wordpress.com/2014/04/08/bill-cooks-tsp-talk-at-the-university-of-wisconsin-madison/ and In pursuit of the traveling salesman : mathematics at the limits of computation /William J. Cook. 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art By Michael Jünger et al. EMU Halle library has an electronic version http://www.nps.navy.mil/orfacpag/resumePages/papers/Dell/Formulettes060425.pdf Formulating Integer Linear Programs: A Rogues’ Gallery Gerald G. Brown and Robert F. Dell Naval Postgraduate School April 2006 trillion-dollar decisions: http://inside.mines.edu/~anewman/capital_planning.pdf and Newman, A., G. Brown, R. Dell, A. Giddings, R. Rosenthal. 2000. An integer linear program to plan procurement and deployment of space and missile assets. NPS technical report NPS-OR-00-005, Naval Postgraduate School, Monterey, CA Building intuition : insights from basic operations management models and principles / edited by Dilip Chhajed and Timothy Lowe chapter: The knapsack problem / John J. Bartholdi available electronically from the EMU library The Golden Ticket: P, NP and the Search for the Impossible http://goldenticket.fortnow.com/ying